package com.jxb.test20241216;

/**
 * 0～n-1中缺失的数字。
 * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
 *
 */
public class MissNumber_offer53II {
    public static void main(String[] args) {
        int[] test1 = {0,1,2,3,5,6,7,8};
        int[] test2 = {1,2,3,4,5,6,7,8};
        int[] test3 = {0,1,2,3,4,5,6,4};
        int[] test4 = {0};
        int[] test5 = {};
        System.out.println(missNumber2(test3));
//        System.out.println(missNumber1(test2));
//        System.out.println(missNumber1(test3));
//        System.out.println(missNumber1(test4));
//        System.out.println(missNumber1(test5));
    }

    public static int missNumber1(int[] nums){
        for (int i = 0;i<nums.length;i++) {
            if (i != nums[i]) {
                return i;
            }
        }
        return -1;
    }

    //通过类似二分查找来找
    //若中间的元素与下标值相等，则直接找右边的
    //若不相等，从左边开始找
    public static int missNumber(int[] nums){
        if (nums==null || nums.length==0) {
            return -1;
        }
        int startIndex = 0;
        int endIndex = nums.length - 1;
        while (startIndex <= endIndex) {
            int mid = (startIndex + endIndex) >> 1;
            if (nums[mid] != mid) {
                //左边结束条件
                if (mid == 0 || nums[mid - 1] == mid - 1) {
                    return mid;
                }else {
                    //下一轮查找只需要查找左半边
                    endIndex = mid - 1;
                }
            }else {
                //下一轮查找只需要查找右半边
                startIndex = mid + 1;
            }
        }

        //处理边界条件，比如边界值测试
        if (startIndex == nums.length) {
            return nums.length;
        }

        //其他情况返回-1
        return -1;
    }

    public static int missNumber2(int[] nums){
        if (nums==null || nums.length==0) {
            return -1;
        }
        int startIndex = 0;
        int endIndex = nums.length - 1;
        while (startIndex <= endIndex) {
            int mid = (startIndex + endIndex) >> 1;
            if (mid != nums[mid]) {
                if (mid == 0 || (mid - 1) == nums[mid - 1]) {
                    return mid;
                }else {
                    endIndex = endIndex - 1;
                }
            }else {
                startIndex = startIndex + 1;
            }
        }
        return -1;
    }

}
